package com.tree.sort;

import cn.hutool.json.JSONUtil;
import com.alibaba.fastjson.JSON;

/**
 * @ClassName com.tree.sort
 * Description: <类功能描述>. <br>
 * <p> 912. 排序数组
冒泡，选择，插入（包括，未随机化的二向、三向切分快排，以及随机化的二向切分）超时；
快速\希尔排序，归并排序，堆排序
桶排序，

 * </p>
 * @Author tree
 * @Date 3/5/24 9:32 PM
 * @Version 1.0
 */
public class Sort {
    public static void main(String[] args) {
        int[] nums = {5,1,1,2,0,0};


//        System.out.println(JSONUtil.toJsonStr(quickSort(nums, 0, nums.length-1)));
//        System.out.println(JSONUtil.toJsonStr(bubbleSort(nums)));
//        System.out.println(JSONUtil.toJsonStr(selectSort(nums)));
//        System.out.println(JSONUtil.toJsonStr(insertSort(nums)));
        System.out.println(JSONUtil.toJsonStr(shellSort(nums)));

    }

    private static int[]  shellSort(int[] arr) {
        int d = arr.length/2;

//        int tmp = 0 , j = 0;
        //希尔排序  升序
        //d：增量 3   1
        for (;d>0;d /= 2){
            System.out.println("增量取值:" + d);
            for (int i = d; i < arr.length; i++){
                //i:代表即将插入的元素角标，作为每一组比较数据的最后一个元素角标
                //j:代表与i同一组的数组元素角标
                //在此处-d 为了避免下面数组角标越界
                for (int j = i-d; j>=0; j-=d){
                    // j+d 代表即将插入的元素所在的角标
                    if (arr[j] > arr[j + d]) {
                        //符合条件，插入元素（交换位置）
                        swap(arr,j,j+d);
                    }
                }
            }
        }
        return arr;
    }

        /**
         * <p>
         * 插入排序
         * 插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
         * 插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
         * 1. 算法步骤
         * 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
         * 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
         * </p>
         * @Author tree
         * @Date 2019-12-10 22:35
         * @Version 1.0
         */
    public static int[] insertSort(int[] arr){
        int tmp;
        for(int i=1;i< arr.length; i++){
            int j = i;
            tmp = arr[i];
            while (j>0 && arr[j-1] > tmp){
                arr[j]= arr[j-1];
                j--;
            }
//            if (j != i) {
                System.out.println(j);
                arr[j ] = tmp;
//            }

        }
        return arr;
    }


    /**
     * 冒泡排序
     *  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
     *
     * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
     *
     * 针对所有的元素重复以上的步骤，除了最后一个。
     *
     * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
     *
     * @author tree
     * @date 2019-10-18 15:56
     */
    public static int[] bubbleSort(int[] arr){
        for (int i =0; i< arr.length; i++){
            // 如果循环没有一次交换， 则代表整个数组已经有序
            boolean flag = true;
            for(int j =1 ;j < arr.length; j++){
                if(arr[j-1] > arr[j]){
                    swap(arr, j, j-1);
                    flag = false;
                }

            }
            if (flag){
                break;
            }
        }
        return arr;

    }

    /**
     * 选择排序
     * 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
     *
     * 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
     *
     * 重复第二步，直到所有元素均排序完毕。
     *
     * @author tree
     * @date 2019-10-18 15:56
     */
    public static int[] selectSort(int[] arr){
        for (int i =0; i< arr.length; i++){
            int min = i;
            for(int j =i+1 ;j < arr.length; j++){
                if(arr[min] > arr[j]){
                    min = j;
                }

            }
            swap(arr,min, i);
        }
        return arr;

    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] =arr[j];
        arr[j] = tmp;
    }

    private static int[] quickSort(int[] nums, int left, int right) {
        if (left < right){
            int pivot = partition(nums, left, right);
            quickSort(nums, left, pivot-1);
            quickSort(nums, pivot+1, right);
        }

        return nums;
    }

    private static int partition(int[] nums, int left, int right) {
        int pivot = nums[left];

        while (left < right){
            while (left<right && nums[right] >= pivot){
                right --;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot;


        return right;
    }

}
